f1, f2 = 1, 1

ten = 10 ** 9

idx = 2

def check(s):
    if len(s) != 9:
        return 0
    if '0' in s:
        return 0
    d = {}
    for c in s:
        d[c] = 1
    return len(d) == 9

print '123456789', check('123456789')
print '098765432', check('098765432')

while 1:
    idx += 1
    f1, f2 = f2, f1 + f2
    mod = f2 % ten
    if check(str(mod)):
        first = str(f2)[:9]
        print idx, first
        if check(first):
            print idx
            break

